# coding: utf-8
# This is the code for the Genetic Algorithm (GA) for TSP.
import random
from copy import deepcopy
import numpy as np
import numpy.random as np_random


def calculate_distance(distance_matrix, order):
    distance_sum = 0.0
    for num in range(len(order)):
        distance_sum += distance_matrix[order[num], order[(num + 1) % (len(order))]]
    return distance_sum


class GA:
    def __init__(self, data, pc=0.7, pm=0.02, pop_size=None, selection_type='WES', crossover_type='PMX',
                 mutation_type='swap', parameter=None, score_type='sum', local_search=False):
        self.name = __class__.__name__
        self.cities, self.city_x, self.city_y = data.cities, data.x, data.y
        self.n = len(self.cities)
        self.Distance = data.distance_matrix
        self.pc, self.pm = pc, pm  # 交叉突变概率
        self.pop_size = int(self.n / 10) + 10 if pop_size is None else pop_size
        self.gene_len = len(self.cities)  # 城市数量
        self.population = []  # 种群
        self.best, self.worse = None, None  # 保存这一代中最好的个体
        self.evolve_list = []
        self.generation = 0
        self.cross_count, self.mutation_count = 0, 0
        self.bounds = 0.0  # 适配值之和，用于选择时计算概率
        self.selection_type, self.crossover_type, self.mutation_type = selection_type, crossover_type, mutation_type
        self.parameter = parameter
        self.score_type = score_type
        self.local_search = local_search
        self.eval = 0
        self.offspring_pop, self.parent_pop, self.grandparent_pop = [], [], []
        self.population_init()  # 初始化种群

    def __repr__(self):
        print(f'N:{self.n};POP:{self.pop_size};Pc:{self.pc};Pm{self.pm};LS:{self.local_search}')
        print(f'Cross:{self.crossover_type};Selection:{self.selection_type};Mutation:{self.mutation_type}')

    class individual(object):
        def __init__(self, gene=None):
            self.gene = gene
            self.score = -1

    def population_init(self):
        self.population = []
        for i in range(self.pop_size):
            gene = list(range(1, self.gene_len + 1))
            random.shuffle(gene)
            individual = self.individual(gene)
            self.population.append(individual)
        self.sale_num = 1

    def judge(self):
        self.choose_selection()
        self.best.score = 1.0 / self.calculate_score(self.best)
        for individual in self.population:
            individual.score = 1.0 / self.calculate_score(individual)
        self.population.sort(key=lambda x: x.score, reverse=True)
        if self.best.score < self.population[0].score:  # 如果新基因的适配值大于原先的best基因，就更新best基因
            self.best = deepcopy(self.population[0])
        self.worse = self.population[-1]

    def calculate_score(self, individual):
        self.eval += 1
        return self.distance(individual)

    def distance(self, individual):
        return calculate_distance(self.Distance, individual.gene)

    def multi_distance(self, target):
        sums = 0
        for r in target:
            sums = sums + calculate_distance(self.Distance, r)
        return sums

    def amend(self, route1, route2, low, high):
        mapping1, mapping2 = dict(), dict()
        for i in range(low, high):
            mapping2[route2[i]], mapping1[route1[i]] = route1[i], route2[i]
        for i in range(low):
            while route1[i] in route1[low:high]:
                route1[i] = mapping1[route1[i]]
            while route2[i] in route2[low:high]:
                route2[i] = mapping2[route2[i]]
        for i in range(high, len(route1)):
            while route1[i] in route1[low:high]:
                route1[i] = mapping1[route1[i]]
            while route2[i] in route2[low:high]:
                route2[i] = mapping2[route2[i]]
        return route1, route2

    def PMX(self, parent1, parent2):
        index1 = random.randint(0, self.gene_len - 1)
        index2 = random.randint(index1, self.gene_len - 1)
        child1 = parent1[0:index1] + parent2[index1:index2] + parent1[index2:self.gene_len]
        child2 = parent2[0:index1] + parent1[index1:index2] + parent2[index2:self.gene_len]
        child1, child2 = self.amend(child1, child2, index1, index2)
        return child1, child2

    def CX(self, parent1, parent2):
        child1, child2 = [-1 for _ in range(self.gene_len)], [-1 for _ in range(self.gene_len)]
        choice = random.randint(0, self.gene_len - 1)
        point = choice
        child1[point], child2[point] = parent1[point], parent2[point]
        for pos in range(self.gene_len):
            if parent1[pos] == parent2[point]:
                point = pos
                break
        while not (point == choice):
            child1[point], child2[point] = parent1[point], parent2[point]
            for pos in range(self.gene_len):
                if parent1[pos] == parent2[point]:
                    point = pos
                    break
        for pos in range(self.gene_len):
            if child1[pos] == -1:
                child1[pos], child2[pos] = parent2[pos], parent1[pos]
        return child1, child2

    def OX(self, parent1, parent2):
        index1 = random.randint(0, self.gene_len - 1)
        index2 = random.randint(index1, self.gene_len - 1)
        child1 = [-1 for _ in range(index1)] + parent1[index1:index2] + [-1 for _ in range(self.gene_len - index2)]
        child2 = [-1 for _ in range(index1)] + parent2[index1:index2] + [-1 for _ in range(self.gene_len - index2)]
        pos1, pos2 = 0, 0
        while (pos1 < self.gene_len) and (pos2 < self.gene_len):
            if parent2[pos1] not in child1:
                if child1[pos2] == -1:
                    child1[pos2] = parent2[pos1]
                else:
                    pos2 += 1
            else:
                pos1 += 1
        pos1, pos2 = 0, 0
        while (pos1 < self.gene_len) and (pos2 < self.gene_len):
            if parent1[pos1] not in child2:
                if child2[pos2] == -1:
                    child2[pos2] = parent1[pos1]
                else:
                    pos2 += 1
            else:
                pos1 += 1
        return child1, child2

    def PBX(self, parent1, parent2):
        choice = [random.randint(0, 1) for _ in range(self.gene_len)]
        child1, child2 = [-1 for _ in range(self.gene_len)], [-1 for _ in range(self.gene_len)]
        for pos in range(self.gene_len):
            if choice[pos] == 1:
                child1[pos], child2[pos] = parent1[pos], parent2[pos]
        pos1, pos2 = 0, 0
        while (pos1 < self.gene_len) and (pos2 < self.gene_len):
            if parent2[pos1] not in child1:
                if child1[pos2] == -1:
                    child1[pos2] = parent2[pos1]
                else:
                    pos2 += 1
            else:
                pos1 += 1
        pos1, pos2 = 0, 0
        while (pos1 < self.gene_len) and (pos2 < self.gene_len):
            if parent1[pos1] not in child2:
                if child2[pos2] == -1:
                    child2[pos2] = parent1[pos1]
                else:
                    pos2 += 1
            else:
                pos1 += 1
        return child1, child2

    def SEX(self, parent1, parent2):
        index1 = random.randint(0, self.gene_len - 1)
        index2 = random.randint(index1, self.gene_len - 1)
        child1, child2, exchange1, exchange2 = parent1, parent2, parent1[index1:index2], []
        for gene in parent2:
            if gene in exchange1:
                exchange2.append(gene)
        pos = 0
        for gene in range(self.gene_len):
            if child2[gene] in exchange1:
                child2[gene] = exchange1[pos]
                pos += 1
        pos = 0
        for gene in range(self.gene_len):
            if child1[gene] in exchange2:
                child1[gene] = exchange2[pos]
                pos += 1
        return child1, child2

    def OBX(self, parent1, parent2):
        choice = [random.randint(0, 1) for _ in range(self.gene_len)]
        choice1, choice2, child1, child2 = [], [], parent2, parent1
        for pos in range(self.gene_len):
            if choice[pos] == 1:
                choice1.append(parent1[pos])
                choice2.append(parent2[pos])
        choice01, choice02 = deepcopy(choice1), deepcopy(choice2)
        pos = 0
        while choice1:
            if child1[pos] in choice01:
                child1[pos] = choice1[0]
                choice1.remove(choice1[0])
            pos += 1
        pos = 0
        while choice2:
            if child2[pos] in choice02:
                child2[pos] = choice2[0]
                choice2.remove(choice2[0])
            pos += 1
        return child1, child2

    def GSX(self, parent1, parent2):
        choice = random.randint(1, self.gene_len)
        pos1, pos2 = parent1.index(choice), parent2.index(choice)
        child1, child2, pos = [choice], [choice], 0
        while len(child1) < self.gene_len:
            if pos % 2 == 0:
                while parent1[pos1] in child1:
                    pos1 = (pos1 + 1) % self.gene_len
                child1.append(parent1[pos1])
            else:
                while parent2[pos2] in child1:
                    pos2 = (pos2 + self.gene_len - 1) % self.gene_len
                child1.insert(0, parent2[pos2])
            pos += 1
        pos1, pos2, pos = parent1.index(choice), parent2.index(choice), 0
        while len(child2) < self.gene_len:
            if pos % 2 == 1:
                while parent1[pos1] in child2:
                    pos1 = (pos1 + 1) % self.gene_len
                child2.append(parent1[pos1])
            else:
                while parent2[pos2] in child2:
                    pos2 = (pos2 + self.gene_len - 1) % self.gene_len
                child2.insert(0, parent2[pos2])
            pos += 1
        return child1, child2

    def APX(self, parent1, parent2):
        child1, child2, pos = [], [], 0
        while len(child1) < self.gene_len:
            if parent1[pos] not in child1:
                child1.append(parent1[pos])
            if parent2[pos] not in child1:
                child1.append(parent2[pos])
            pos += 1
        pos = 0
        while len(child2) < self.gene_len:
            if parent2[pos] not in child2:
                child2.append(parent2[pos])
            if parent1[pos] not in child2:
                child2.append(parent1[pos])
            pos += 1
        return child1, child2

    def ERX(self, parent1, parent2):
        edge_list = [[] for _ in range(self.gene_len)]
        for pos in range(self.gene_len):
            if parent1[(pos + 1) % self.gene_len] not in edge_list[parent1[pos] - 1]:
                edge_list[parent1[pos] - 1].append(parent1[(pos + 1) % self.gene_len])
            if parent1[(pos + self.gene_len - 1) % self.gene_len] not in edge_list[parent1[pos] - 1]:
                edge_list[parent1[pos] - 1].append(parent1[(pos + self.gene_len - 1) % self.gene_len])
            if parent2[(pos + 1) % self.gene_len] not in edge_list[parent2[pos] - 1]:
                edge_list[parent2[pos] - 1].append(parent2[(pos + 1) % self.gene_len])
            if parent2[(pos + self.gene_len - 1) % self.gene_len] not in edge_list[parent2[pos] - 1]:
                edge_list[parent2[pos] - 1].append(parent2[(pos + self.gene_len - 1) % self.gene_len])
        edge_count = [len(edge_list[pos]) for pos in range(len(edge_list))]
        choice = random.randint(1, self.gene_len)
        child, rank = [choice], 0
        while len(child) < self.gene_len:
            next_choice = self.list_min(edge_count, edge_list[choice - 1], rank)
            if next_choice is None:
                break
            if next_choice in child:
                rank += 1
            else:
                edge_list = self.remove_all(edge_list, [choice])
                choice = next_choice
                child.append(choice)
                rank = 0
        pos = 0
        while len(child) < self.gene_len:
            if parent1[pos] not in child:
                child.append(parent1[pos])
            pos += 1
        return child

    def remove_all(self, a, e):
        b = []
        for ee in a:
            if ee not in e:
                b.append(ee)
            else:
                continue
        return b

    def list_min(self, target_list, target, rank):
        if rank < len(target):
            random.shuffle(target)
            sum_list = []
            for i in target:
                sum_list.append(target_list[i - 1])
            sort_list = sorted(sum_list)
            outcome = sum_list.index(sort_list[rank])
            return target[outcome]
        else:
            return None

    def MPX(self, parent1, parent2):
        if self.gene_len > 20:
            choice = random.randint(10, int(self.gene_len / 2))
        else:
            choice = random.randint(1, int(self.gene_len / 2))
        index = random.randint(0, self.gene_len - choice - 1)
        child1 = [-1 for _ in range(index)] + parent1[index:index + choice] + [-1 for _ in
                                                                               range(self.gene_len - index - choice)]
        child2 = [-1 for _ in range(index)] + parent2[index:index + choice] + [-1 for _ in
                                                                               range(self.gene_len - index - choice)]
        pos1, pos2 = 0, 0
        while (pos1 < self.gene_len) and (pos2 < self.gene_len):
            if parent2[pos1] not in child1:
                if child1[pos2] == -1:
                    child1[pos2] = parent2[pos1]
                else:
                    pos2 += 1
            else:
                pos1 += 1
        pos1, pos2 = 0, 0
        while (pos1 < self.gene_len) and (pos2 < self.gene_len):
            if parent1[pos1] not in child2:
                if child2[pos2] == -1:
                    child2[pos2] = parent1[pos1]
                else:
                    pos2 += 1
            else:
                pos1 += 1
        return child1, child2

    def ULX(self, parent1, parent2):
        child1, child2, rest1, rest2 = [-1 for _ in range(self.gene_len)], [-1 for _ in range(self.gene_len)], [], []
        for pos in range(self.gene_len):
            if parent1[pos] == parent2[pos]:
                child1[pos], child2[pos] = parent1[pos], parent1[pos]
        for city in parent1:
            if city not in child1:
                rest1.append(city)
                rest2.append(city)
        pos = 0
        while rest1:
            if child1[pos] == -1:
                if parent1[pos] not in child1 and parent2[pos] not in child1:
                    choice = parent1[pos] if random.randint(0, 1) else parent2[pos]
                elif parent1[pos] not in child1:
                    choice = parent1[pos]
                elif parent2[pos] not in child1:
                    choice = parent2[pos]
                else:
                    choice = random.choice(rest1)
                child1[pos] = choice
                rest1.remove(choice)
            pos += 1
        pos = self.gene_len - 1
        while rest2:
            if child2[pos] == -1:
                if parent1[pos] not in child2 and parent2[pos] not in child2:
                    choice = parent1[pos] if random.randint(0, 1) else parent2[pos]
                elif parent1[pos] not in child2:
                    choice = parent1[pos]
                elif parent2[pos] not in child2:
                    choice = parent2[pos]
                else:
                    choice = random.choice(rest2)
                child2[pos] = choice
                rest2.remove(choice)
            pos -= 1
        return child1, child2

    def EXX(self, parent1, parent2):
        i1, i2, j1, j2, count = random.randint(1, self.gene_len), -1, -1, -1, 0
        ori, child1, child2 = i1, parent1, parent2
        while (parent1 == child1) and (count < self.gene_len):
            edge1, edge2 = [], []
            for pos in range(self.gene_len):
                edge1.append([parent1[pos], parent1[(pos + 1) % self.gene_len]])
                edge2.append([parent2[pos], parent2[(pos + 1) % self.gene_len]])
            i1 = (ori + count) % self.gene_len
            for pos in range(self.gene_len):
                if parent2[pos] == parent1[i1]:
                    i2 = pos
                    break
            edge1[i1], edge2[i2] = deepcopy(edge2[i2]), deepcopy(edge1[i1])
            while not edge1[i1][1] == edge2[i2][1]:
                for pos in range(self.gene_len):
                    if edge1[pos][0] == edge1[i1][1]:
                        j1 = pos
                        break
                for pos in range(self.gene_len):
                    if edge2[pos][0] == edge2[i2][1]:
                        j2 = pos
                        break
                for pos in range(int(((j1 + self.gene_len - i1) % self.gene_len + 1) / 2) - 1):
                    edge1[(i1 + pos + 1) % self.gene_len], edge1[
                        (j1 + self.gene_len - pos - 1) % self.gene_len] = deepcopy(
                        edge1[(j1 + self.gene_len - pos - 1) % self.gene_len]), deepcopy(
                        edge1[(i1 + pos + 1) % self.gene_len])
                for pos in range(i1 + 1, (j1 + self.gene_len - i1) % self.gene_len + i1):
                    edge1[pos % self.gene_len][0], edge1[pos % self.gene_len][1] = edge1[pos % self.gene_len][1], \
                                                                                   edge1[pos % self.gene_len][0]
                for pos in range(int(((j2 + self.gene_len - i2) % self.gene_len + 1) / 2) - 1):
                    edge2[(i2 + pos + 1) % self.gene_len], edge2[
                        (j2 + self.gene_len - pos - 1) % self.gene_len] = deepcopy(
                        edge2[(j2 + self.gene_len - pos - 1) % self.gene_len]), deepcopy(
                        edge2[(i2 + pos + 1) % self.gene_len])
                for pos in range(i2 + 1, (j2 + self.gene_len - i2) % self.gene_len + i2):
                    edge2[pos % self.gene_len][0], edge2[pos % self.gene_len][1] = edge2[pos % self.gene_len][1], \
                                                                                   edge2[pos % self.gene_len][0]
                i1, i2 = j1, j2
                edge1[i1], edge2[i2] = deepcopy(edge2[i2]), deepcopy(edge1[i1])
            child1, child2 = [], []
            for pos in range(self.gene_len):
                child1.append(edge1[pos][0])
                child2.append(edge2[pos][0])
            count += 1
        return child1, child2

    def HX(self, parent1, parent2):
        edge_list = [[] for _ in range(self.gene_len)]
        for pos in range(self.gene_len):
            if parent1[(pos + 1) % self.gene_len] not in edge_list[parent1[pos] - 1]:
                edge_list[parent1[pos] - 1].append(parent1[(pos + 1) % self.gene_len])
            if parent1[(pos + self.gene_len - 1) % self.gene_len] not in edge_list[parent1[pos] - 1]:
                edge_list[parent1[pos] - 1].append(parent1[(pos + self.gene_len - 1) % self.gene_len])
            if parent2[(pos + 1) % self.gene_len] not in edge_list[parent2[pos] - 1]:
                edge_list[parent2[pos] - 1].append(parent2[(pos + 1) % self.gene_len])
            if parent2[(pos + self.gene_len - 1) % self.gene_len] not in edge_list[parent2[pos] - 1]:
                edge_list[parent2[pos] - 1].append(parent2[(pos + self.gene_len - 1) % self.gene_len])
        choice1, choice2 = random.randint(1, self.gene_len), random.randint(1, self.gene_len)
        rest1, rest2, child1, child2 = list(range(1, self.gene_len + 1)), list(range(1, self.gene_len + 1)), [
            choice1], [choice2]
        while len(child1) < self.gene_len:
            rest1.remove(choice1)
            next_choice = edge_list[choice1 - 1][0]
            for edge in edge_list[choice1 - 1]:
                if self.Distance[choice1 - 1][edge] < self.Distance[choice1 - 1][next_choice]:
                    next_choice = edge
            choice1 = random.choice(rest1) if (next_choice not in rest1) else next_choice
            child1.append(choice1)
        while len(child2) < self.gene_len:
            rest2.remove(choice2)
            next_choice = edge_list[choice2 - 1][0]
            for edge in edge_list[choice2 - 1]:
                if self.Distance[choice2 - 1][edge] < self.Distance[choice2 - 1][next_choice]:
                    next_choice = edge
            choice2 = random.choice(rest2) if (next_choice not in rest2) else next_choice
            child2.append(choice2)
        return child1, child2

    def SCX(self, parent1, parent2):
        choice = parent1[0]
        child1, rest = [choice], list(range(1, self.gene_len + 1))
        rest.remove(choice)
        while len(child1) < self.gene_len:
            pos1, pos2 = parent1.index(choice), parent2.index(choice)
            next1 = parent1[(pos1 + 1) % self.gene_len] if (parent1[(pos1 + 1) % self.gene_len] not in child1) else \
                rest[0]
            next2 = parent2[(pos2 + 1) % self.gene_len] if (parent2[(pos2 + 1) % self.gene_len] not in child1) else \
                rest[0]
            choice = next1 if (self.Distance[choice][next1] < self.Distance[choice][next2]) else next2
            child1.append(choice)
            rest.remove(choice)
        choice = parent1[self.gene_len - 1]
        child2, rest = [choice], list(range(1, self.gene_len + 1))
        rest.remove(choice)
        while len(child2) < self.gene_len:
            pos1, pos2 = parent1.index(choice), parent2.index(choice)
            next1 = parent1[(pos1 - 1) % self.gene_len] if (parent1[(pos1 - 1) % self.gene_len] not in child2) else \
                rest[0]
            next2 = parent2[(pos2 - 1) % self.gene_len] if (parent2[(pos2 - 1) % self.gene_len] not in child2) else \
                rest[0]
            choice = next1 if (self.Distance[choice][next1] < self.Distance[choice][next2]) else next2
            child2.append(choice)
            rest.remove(choice)
        return child1, child2

    def GNX(self, parent1, parent2, parameter=4):
        index = [0]
        child1, child2 = [-1 for _ in range(self.gene_len)], [-1 for _ in range(self.gene_len)]
        for i in range(parameter):
            index.append(random.randint(index[-1] + 1, self.gene_len - parameter - 1 + i))
        index.append(self.gene_len - 1)
        for i in range(parameter + 1):
            if i % 2 == 0:
                child1[index[i]:index[i + 1]] = parent1[index[i]:index[i + 1]]
                child2[index[i]:index[i + 1]] = parent2[index[i]:index[i + 1]]
        for pos in range(self.gene_len):
            if child1[pos] == -1:
                if parent2[pos] not in child1:
                    child1[pos] = parent2[pos]
            if child2[pos] == -1:
                if parent1[pos] not in child2:
                    child2[pos] = parent1[pos]
        rest1, rest2, city_list, pos = [], [], list(range(1, self.gene_len + 1)), 0
        random.shuffle(city_list)
        for city in city_list:
            if city not in child1:
                rest1.append(city)
            if city not in child2:
                rest2.append(city)
        pos = 0
        while rest1:
            if child1[pos] == -1:
                child1[pos] = rest1[0]
                rest1.remove(rest1[0])
            pos += 1
        pos = 0
        while rest2:
            if child2[pos] == -1:
                child2[pos] = rest2[0]
                rest2.remove(rest2[0])
            pos += 1
        return child1, child2

    def ZX(self, parent1, parent2):
        alpha = random.uniform(0.1, 0.8)
        lx, ly = (max(self.city_x) - min(self.city_x)) * alpha, (max(self.city_y) - min(self.city_y)) * alpha
        choice = random.randint(1, self.gene_len)
        mid_x, mid_y, flag = self.city_x[choice], self.city_y[choice], [True]
        for pos in range(self.gene_len):
            if abs(self.city_x[pos] - mid_x) < lx / 2 and abs(self.city_y[pos] - mid_y) < ly / 2:
                flag.append(True)
            else:
                flag.append(False)
        if True not in flag[1::] or False not in flag[1::]:
            return parent1, parent2
        offspring1, offspring2, child = deepcopy([parent1]), deepcopy([parent2]), [[], []]
        for pos in range(self.gene_len - 1):
            if flag[parent1[pos]] ^ flag[parent1[pos + 1]]:
                offspring1.append(parent1[pos + 1:])
                for i in range(len(offspring1[-1])):
                    offspring1[-2].remove(offspring1[-1][i])
        if flag[parent1[-1]] ^ flag[parent1[0]] == 0:
            offspring1[-1] = offspring1[-1] + offspring1[0]
            offspring1 = offspring1[1:]
        for pos in range(len(parent1) - 1):
            if flag[parent2[pos]] ^ flag[parent2[pos + 1]]:
                offspring2.append(parent2[pos + 1:])
                for i in range(len(offspring2[-1])):
                    offspring2[-2].remove(offspring2[-1][i])
        if flag[parent2[-1]] ^ flag[parent2[0]] == 0:
            offspring2[-1] = offspring2[-1] + offspring2[0]
            offspring2 = offspring2[1:]
        for i in range(len(offspring1)):
            if flag[offspring1[i][0]]:
                child[0].append(offspring1[i])
            else:
                child[1].append(offspring1[i])
        for i in range(len(offspring2)):
            if flag[offspring2[i][0]]:
                child[1].append(offspring2[i])
            else:
                child[0].append(offspring2[i])
        for num in range(2):
            while len(child[num]) > 1:
                target, flag = 1, False
                for i in range(1, len(child[num])):
                    if self.Distance[child[num][i][0]][child[num][0][-1]] < \
                            self.Distance[child[num][target][0]][child[num][0][-1]]:
                        target = i
                for i in range(1, len(child[num])):
                    if not flag:
                        if self.Distance[child[num][i][-1]][child[num][0][-1]] < \
                                self.Distance[child[num][target][0]][child[num][0][-1]]:
                            target = i
                    else:
                        if self.Distance[child[num][i][-1]][child[num][0][-1]] < \
                                self.Distance[child[num][target][-1]][child[num][0][-1]]:
                            target = i
                if flag:
                    child[num][0] = child[num][0] + reversed(child[num][target])
                else:
                    child[num][0] = child[num][0] + child[num][target]
                child[num].remove(child[num][target])
            child[num] = child[num][0]
        return child[0], child[1]

    def edges2route(self, edges, ab_circle=False):
        if ab_circle:
            route, belongs = [], []
            while edges:
                belongs.append(edges[0][-1])
                route.append(edges[0][0:2])
                edges.remove(edges[0])
                while route[-1][-1] != route[-1][0]:
                    for edge in edges:
                        if route[-1][-1] in edge:
                            route[-1].append(edge[1 - edge.index(route[-1][-1])])
                            edges.remove(edge)
                            break
            for i in range(len(route)):
                route[i] = [route[i][0:len(route[i]) - 1], belongs[i]]
        else:
            route = []
            while edges:
                route.append(edges[0])
                edges.remove(edges[0])
                while route[-1][-1] != route[-1][0]:
                    for edge in edges:
                        if route[-1][-1] in edge:
                            route[-1].append(edge[1 - edge.index(route[-1][-1])])
                            edges.remove(edge)
                            break
            for i in range(len(route)):
                route[i] = route[i][0:len(route[i]) - 1]
        return route

    def route2edges(self, routes, ab_circle=False):
        edges = []
        if ab_circle:
            for route in routes:
                for i in range(len(route[0])):
                    if route[-1] == 'p1':
                        belongs = 'p2' if i % 2 else 'p1'
                    else:
                        belongs = 'p1' if i % 2 else 'p2'
                    edges.append([route[0][i], route[0][(i + 1) % len(route[0])], belongs])
        else:
            for route in routes:
                for i in range(len(route)):
                    edges.append([route[i], route[(i + 1) % len(route)]])
        return edges

    def edges2ABroute(self, edges):
        route, belongs = [], []
        while edges:
            flag = 1 if edges[0][-1] == 'p1' else 0  # 0 stands for p1 and 1 stands for p2
            belongs.append(edges[0][-1])
            route.append(edges[0][0:2])
            edges.remove(edges[0])
            while route[-1][-1] != route[-1][0] or (len(route[-1]) % 2 == 0):
                for edge in edges:
                    if route[-1][-1] in edge and ((edge[-1] == 'p1') ^ flag):
                        route[-1].append(edge[1 - edge.index(route[-1][-1])])
                        edges.remove(edge)
                        flag = 1 - flag
                        break
        for i in range(len(route)):
            route[i] = [route[i][0:len(route[i]) - 1], belongs[i]]
        return route

    def decrease_circle(self, circle):
        rk = [calculate_distance(self.Distance, i) for i in circle]
        rk = circle[rk.index(min(rk))]
        circle.remove(rk)
        if len(rk) < 2:
            return self.insert_tour(circle, rk)
        best_a, best_b, best_r = 0, 0, 0
        best = self.Distance[rk[0]][rk[1]] + self.Distance[circle[0][0]][circle[0][1]] \
               - self.Distance[rk[0]][circle[0][0]] - self.Distance[rk[1]][circle[0][1]]
        flag = 0
        for a in range(len(rk)):
            for r in range(len(circle)):
                for b in range(len(circle[r])):
                    temp = self.Distance[rk[a]][rk[(a + 1) % len(rk)]] + \
                           self.Distance[circle[r][b]][circle[r][(b + 1) % len(circle[r])]] - \
                           self.Distance[rk[a]][circle[r][b]] - \
                           self.Distance[rk[(a + 1) % len(rk)]][circle[r][(b + 1) % len(circle[r])]]
                    if temp > best:
                        best, best_a, best_b, best_r = temp, a, b, r
        rk = rk[::-1]
        for a in range(len(rk)):
            for r in range(len(circle)):
                for b in range(len(circle[r])):
                    temp = self.Distance[rk[a]][rk[(a + 1) % len(rk)]] + \
                           self.Distance[circle[r][b]][circle[r][(b + 1) % len(circle[r])]] - \
                           self.Distance[rk[a]][circle[r][b]] - \
                           self.Distance[rk[(a + 1) % len(rk)]][circle[r][(b + 1) % len(circle[r])]]
                    if temp > best:
                        flag = 1
                        best, best_a, best_b, best_r = temp, a, b, r
        if not flag:
            rk = rk[::-1]
        rk = rk[best_a + 1:] + rk[:best_a + 1] if (best_a + 1) % len(rk) else rk
        circle[best_r] = circle[best_r][best_b + 1:] + circle[best_r][:best_b + 1] \
            if (best_b + 1) % len(circle[best_r]) else circle[best_r]
        circle[best_r] = circle[best_r] + rk[::-1]
        return circle

    def EAX(self, parent1, parent2, illegal_amend=False):
        edge1 = [[parent1[i], parent1[(i + 1) % self.gene_len], 'p1'] for i in range(self.gene_len)]
        edge2 = [[parent2[i], parent2[(i + 1) % self.gene_len], 'p2'] for i in range(self.gene_len)]
        ab_set = self.edges2ABroute(edge1 + edge2)
        ab_set2 = self.remove_all([i if len(i[0]) < 3 else [] for i in ab_set], [[]])
        ab_set = self.remove_all([i if len(i[0]) > 2 else [] for i in ab_set], [[]])
        if illegal_amend:
            while ab_set2:
                choice, next_city, index, ab_setlist = ab_set2[0][0], -1, -1, [i[0] for i in ab_set]
                for city in choice:
                    for route in range(len(ab_setlist)):
                        if city in ab_setlist[route]:
                            index, next_city = route, city
                            break
                if index > -1:
                    pos = ab_set[index][0].index(next_city)
                    ab_set[index][0] = ab_set[index][0][0:pos] + [next_city] + [choice[1 - choice.index(next_city)]] + \
                                       ab_set[index][0][pos::]
                    ab_set2.remove(ab_set2[0])
                else:
                    ab_setlist = [i[0] for i in ab_set2[1::]]
                    for city in choice:
                        for route in range(len(ab_setlist)):
                            if city in ab_setlist[route]:
                                index = route
                                next_city = city
                                break
                    ab_set2[index][0] = [next_city] + [choice[1 - choice.index(next_city)]] + [next_city] + [
                        ab_set2[index + 1][0][1 - ab_set2[index + 1][0].index(next_city)]]
                    ab_set.append(ab_set2[index])
                    ab_set2.remove(ab_set2[index])
                    ab_set2.remove(ab_set2[0])
        e_set1, e_set2 = self.block(ab_set, parent1, parent2, block_type='default')
        e_set_edges1, e_set_edges2 = self.route2edges(e_set1, ab_circle=True), self.route2edges(e_set2, ab_circle=True)
        off_edge1, off_edge2 = deepcopy(edge1), deepcopy(edge2)
        for edge in e_set_edges1:
            if edge[-1] == 'p1':
                if edge in off_edge1:
                    off_edge1.remove(edge)
                else:
                    off_edge1.remove(edge[0:2][::-1] + [edge[-1]])
            else:
                off_edge1.append(edge)
        for edge in e_set_edges2:
            if edge[-1] == 'p1':
                off_edge2.append(edge)
            else:
                if edge in off_edge2:
                    off_edge2.remove(edge)
                else:
                    off_edge2.remove(edge[0:2][::-1] + [edge[-1]])
        off_edge1, off_edge2 = self.edges2route(off_edge1, ab_circle=True), self.edges2route(off_edge2, ab_circle=True)
        off = [[i[0] for i in off_edge1], [i[0] for i in off_edge2]]
        for num in range(len(off)):
            while len(off[num]) > 1:
                off[num] = self.decrease_circle(off[num])
        return off[0][0], off[1][0]

    def block(self, ab_set, parent1=None, parent2=None, block_type='default'):
        if len(ab_set) < 1:
            return ab_set, ab_set
        else:
            if block_type == 'default':
                ab_set.sort(key=lambda x: len(x[0]), reverse=True)
                e_set = [ab_set[0]]
                for i in range(len(ab_set) - int(len(ab_set) / 2), len(ab_set)):
                    for city in ab_set[i][0]:
                        if city in e_set[0][0]:
                            e_set.append(ab_set[i])
                            break
                return e_set, e_set
            elif block_type == 'block':
                ab_set.sort(key=lambda x: len(x[0]), reverse=True)
                e_set = [ab_set[1]] if len(ab_set) > 1 else [ab_set[-1]]
                off_edge1 = [[parent1[i], parent1[(i + 1) % self.gene_len], 'p1'] for i in range(self.gene_len)]
                off_edge2 = [[parent2[i], parent2[(i + 1) % self.gene_len], 'p2'] for i in range(self.gene_len)]
                e_set_edges = self.route2edges(e_set)
                e_set1, e_set2 = deepcopy(e_set), deepcopy(e_set)
                ab_set = ab_set[2:] if len(ab_set) > 2 else []
                for edge in e_set_edges:
                    if edge[-1] == 'p1':
                        if edge in off_edge1:
                            off_edge1.remove(edge)
                        else:
                            off_edge1.remove(edge[0:2][::-1] + [edge[-1]])
                        off_edge2.append(edge)
                    else:
                        if edge in off_edge2:
                            off_edge2.remove(edge)
                        else:
                            off_edge2.remove(edge[0:2][::-1] + [edge[-1]])
                        off_edge1.append(edge)
                off_edge1, off_edge2 = self.edges2route(off_edge1), self.edges2route(off_edge2)
                off_edge1.sort(key=lambda x: len(x[0]), reverse=True)
                off_edge2.sort(key=lambda x: len(x[0]), reverse=True)
                off_edge1, off_edge2 = off_edge1[1:], off_edge2[1:]
                off1, off2 = [], []
                for r in off_edge1:
                    off1 = off1 + r[0]
                for r in off_edge2:
                    off2 = off2 + r[0]
                for r in ab_set:
                    for c in r[0]:
                        if c in off1:
                            e_set1.append(r)
                            break
                    for c in r[0]:
                        if c in off2:
                            e_set2.append(r)
                            break
                return e_set1, e_set2
            elif block_type == 'rand':
                e_set1, e_set2 = [], []
                for i in ab_set:
                    if random.random() > 0.5:
                        e_set1.append(i)
                    if random.random() > 0.5:
                        e_set2.append(i)
                return e_set1, e_set2
            elif block_type == 'big':
                ab_set.sort(key=lambda x: len(x[0]), reverse=True)
                e_set = [ab_set[0]]
                ab_set = ab_set[1:]
                for r in ab_set:
                    for c in r[0]:
                        if c in e_set[0][0]:
                            e_set.append(r)
                            break
                return e_set, e_set
            else:
                raise TypeError('undefined block_type')

    def insert_tour(self, routes, tour, pick_type='roulette'):
        if pick_type == 'random':
            r = random.randint(0, len(routes) - 1)
            p = random.randint(0, len(routes[r]) - 1)
            flag = random.randint(0, 1)
        else:
            rlist, plist, llist, flag_list, flag = [], [], [], [], 0
            for i in range(2):
                for r in range(len(routes)):
                    for p in range(len(routes[r])):
                        temp = self.Distance[routes[r][p]][tour[0]] + \
                               self.Distance[routes[r][(p + 1) % len(routes[r])]][tour[-1]] - \
                               self.Distance[routes[r][p]][routes[r][(p + 1) % len(routes[r])]]
                        rlist.append(r)
                        plist.append(p)
                        llist.append(temp)
                        flag_list.append(flag)
                if len(tour) < 2:
                    break
                tour, flag = tour[::-1], 1 - flag
            if pick_type == 'greedy':
                choice = llist.index(min(llist))
            elif pick_type == 'roulette':
                eta = 1
                pos = [(max(llist) - i + eta) / (max(llist) - min(llist) + eta) for i in llist]
                pos = [i / sum(pos) for i in pos]
                choice = np_random.choice(list(range(len(pos))), size=1, replace=False, p=pos)[0]
            else:
                raise TypeError('undefined pick_type')
            r, p, flag = rlist[choice], plist[choice], flag_list[choice]
        tour = tour[::-1] if flag else tour
        routes[r] = routes[r][p + 1:] + routes[r][:p + 1] if (p + 1) % len(routes[r]) else routes[r]
        routes[r] = routes[r] + tour
        return routes

    def delete_city(self, routes, pick_type='roulette'):
        if pick_type == 'random':
            r_list = self.remove_all([i if len(routes[i]) > 2 else None for i in range(len(routes))], [None])
            r = random.choice(r_list)
            p = random.randint(0, len(routes[r]) - 1)
        else:
            rlist, plist, llist = [], [], []
            for r in range(len(routes)):
                if len(routes[r]) < 3:
                    continue
                for p in range(len(routes[r])):
                    temp = self.Distance[routes[r][p]][routes[r][(p - 1 + len(routes[r])) % len(routes[r])]] + \
                           self.Distance[routes[r][p]][routes[r][(p + 1) % len(routes[r])]] - \
                           self.Distance[routes[r][(p - 1 + len(routes[r])) % len(routes[r])]][
                               routes[r][(p + 1) % len(routes[r])]]
                    rlist.append(r)
                    plist.append(p)
                    llist.append(temp)
            if pick_type == 'greedy':
                choice = llist.index(max(llist))
            elif pick_type == 'roulette':
                eta = 1
                pos = [(i - min(llist) + eta) / (max(llist) - min(llist) + eta) for i in llist]
                pos = [i / sum(pos) for i in pos]
                choice = np_random.choice(list(range(len(pos))), size=1, replace=False, p=pos)[0]
            else:
                raise "undefined pick_type"
            r, p = rlist[choice], plist[choice]
        city = routes[r][p]
        routes[r].remove(city)
        return routes, city

    def choose_crossover(self, parent1, parent2):
        if self.crossover_type == 'PMX':
            child1, child2 = self.PMX(parent1, parent2)
        elif self.crossover_type == 'OX':
            child1, child2 = self.OX(parent1, parent2)
        elif self.crossover_type == 'CX':
            child1, child2 = self.CX(parent1, parent2)
        elif self.crossover_type == 'PBX':
            child1, child2 = self.PBX(parent1, parent2)
        elif self.crossover_type == 'SEX':
            child1, child2 = self.PBX(parent1, parent2)
        elif self.crossover_type == 'OBX':
            child1, child2 = self.OBX(parent1, parent2)
        elif self.crossover_type == 'GSX':
            child1, child2 = self.GSX(parent1, parent2)
        elif self.crossover_type == 'APX':
            child1, child2 = self.APX(parent1, parent2)
        elif self.crossover_type == 'ERX':
            child1 = self.ERX(parent1, parent2)
            child2 = self.ERX(parent1, parent2)
        elif self.crossover_type == 'MPX':
            child1, child2 = self.MPX(parent1, parent2)
        elif self.crossover_type == 'ULX':
            child1, child2 = self.ULX(parent1, parent2)
        elif self.crossover_type == 'EXX':
            child1, child2 = self.EXX(parent1, parent2)
        elif self.crossover_type == 'HX':
            child1, child2 = self.HX(parent1, parent2)
        elif self.crossover_type == 'SCX':
            child1, child2 = self.SCX(parent1, parent2)
        elif self.crossover_type == 'GNX':
            child1, child2 = self.GNX(parent1, parent2) if self.parameter is None else self.GNX(parent1, parent2,
                                                                                                self.parameter)
        elif self.crossover_type == 'ZX':
            child1, child2 = self.ZX(parent1, parent2)
        elif self.crossover_type == 'EAX':
            child1, child2 = self.EAX(parent1, parent2)
        else:
            raise TypeError('undefined crossover')
        self.cross_count += 1
        return child1, child2

    def choose_mutation(self, gene):
        if self.mutation_type == 'swap':
            gene = self.swap(gene)
        elif self.mutation_type == 'twoopt':
            gene = self.twoopt(gene)
        elif self.mutation_type == 'shuffle1':
            gene = self.shuffle1(gene)
        elif self.mutation_type == 'shuffle2':
            gene = self.shuffle2(gene)
        elif self.mutation_type == 'insert':
            gene = self.insert(gene)
        else:
            raise TypeError('undefined mutation')
        self.mutation_count += 1
        return gene

    def choose_selection(self):
        if self.selection_type == 'WES':
            self.WES()
        elif self.selection_type == 'POES':
            self.POES()
        elif self.selection_type == 'CGES':
            self.CGES()
        else:
            raise TypeError('undefined selection')

    def WES(self):
        pass

    def POES(self):
        self.parent_pop = self.offspring_pop
        self.offspring_pop = self.population
        self.population = self.population + self.parent_pop

    def CGES(self):
        self.grandparent_pop = self.parent_pop
        self.parent_pop = self.offspring_pop
        self.offspring_pop = self.population
        self.population = self.population + self.grandparent_pop

    def swap(self, gene):
        gene_len = len(gene)
        index1, index2 = random.randint(0, gene_len - 1), random.randint(0, gene_len - 1)
        gene[index1], gene[index2] = gene[index2], gene[index1]
        return gene

    def twoopt(self, gene):
        index1 = random.randint(0, len(gene))
        index2 = random.randint(index1, len(gene))
        gene[index1:index2] = gene[index1:index2][::-1]
        return gene

    def shuffle1(self, gene):
        index1, index2, gene_len = 0, 0, len(gene)
        while index1 == index2:
            index1 = random.randint(0, gene_len - 1)
            index2 = random.randint(0, gene_len - 1)
        gene_list = []
        for position in range((index2 - index1 + gene_len) % gene_len):
            gene_list.append(gene[(index1 + position) % gene_len])
        random.shuffle(gene_list)
        for position in range((index2 - index1 + gene_len) % gene_len):
            gene[(index1 + position) % gene_len] = gene_list[position]
        return gene

    def insert(self, gene):
        gene_len = len(gene)
        index1, index2 = random.randint(0, gene_len - 1), random.randint(0, gene_len - 1)
        temp = gene[index1]
        gene.remove(temp)
        gene.insert(index2, temp)
        return gene

    def shuffle2(self, gene):
        gene_len, gene_list, list_pos = len(gene), [], 0
        shuffle_list = [random.randint(0, 1) for _ in range(gene_len)]
        for position in range(gene_len):
            if shuffle_list[position]:
                gene_list.append(gene[position])
        random.shuffle(gene_list)
        position = 0
        while list_pos < len(gene_list):
            if shuffle_list[position]:
                gene[position] = gene_list[list_pos]
                position, list_pos = position + 1, list_pos + 1
            else:
                position += 1
        return gene

    def selection(self):
        self.population.sort(key=lambda x: x.score, reverse=True)
        self.bounds = sum([i.score for i in self.population])
        population_new = [deepcopy(self.best), self.population[0]]
        # population_new = [deepcopy(self.best)]
        prob = [self.population[i].score / self.bounds for i in range(len(self.population))]
        while len(population_new) < self.pop_size:
            population_new.append(np.random.choice(self.population, replace=True, p=prob))
        self.population = population_new

    def crossover(self):
        population_new = []
        random.shuffle(self.population)
        for i in range(int(self.pop_size / 2)):
            if random.random() < self.pc:
                parent1, parent2 = self.population[i * 2], self.population[i * 2 + 1]
                child1, child2 = self.choose_crossover(parent1.gene, parent2.gene)
                child1, child2 = self.individual(child1), self.individual(child2)
            else:
                child1, child2 = self.population[i * 2], self.population[i * 2 + 1]
            population_new.append(child1)
            population_new.append(child2)
        while len(population_new) < self.pop_size:
            population_new.append(self.population[-1])
        self.population = population_new

    def mutation(self):
        for i in range(self.pop_size):
            if random.random() < self.pm:
                self.population[i].gene = self.choose_mutation(self.population[i].gene)

    def twoopt_LS(self, route):
        gene_len = len(route)
        for index1 in range(len(route)):
            for index2 in range(index1, len(route) - 1):
                if self.Distance[route[(index1 - 1 + gene_len) % gene_len]][route[index2]] + \
                        self.Distance[route[index1]][route[(index2 + 1) % gene_len]] < \
                        self.Distance[route[(index1 - 1 + gene_len) % gene_len]][route[index1]] + \
                        self.Distance[route[index2]][route[(index2 + 1) % gene_len]]:
                    route[index1:index2 + 1] = route[index1:index2 + 1][::-1]
                    return route
        return route

    def LocalSearch(self, local_search=False):
        if self.local_search or local_search:
            self.best.gene = self.twoopt_LS(self.best.gene)
            for i in range(len(self.population)):
                self.population[i].gene = self.twoopt_LS(self.population[i].gene)

    def generation_new(self):
        self.selection()
        self.crossover()
        self.mutation()
        self.LocalSearch()
        self.generation += 1
        self.judge()

    def optimize(self, eval_set=None, gen_set=None, display=True, count=None):
        self.best = deepcopy(self.population[0])
        self.judge()
        if eval_set is None:
            eval_set = self.n * 1000
        while self.eval <= eval_set:
            self.generation_new()
            best_route_distance = self.distance(self.best)
            self.evolve_list.append(best_route_distance)
            if display:
                if count is not None:
                    print(f'\rNo.{str(count).zfill(2)}: {self.generation}  {best_route_distance:.4f}', end='')
                else:
                    print(f'\r{self.generation}  {best_route_distance:.4f}', end='')
            if gen_set is not None and self.generation >= gen_set:
                break
        if display:
            print('')
        return self.best

    def draw_route(self, data, plt, individual, show_text=False, show_route=True):
        route = deepcopy(individual.gene)
        route.append(route[0])
        if show_route:
            print('\nbest route:', route)
        data.draw(plt, route=route, show_text=show_text)

    def intersect(self, edge1, edge2):
        a1, b1, a2, b2 = edge1[0], edge1[1], edge2[0], edge2[1]
        l1 = [self.city_x[a1], self.city_y[a1], self.city_x[b1], self.city_y[b1]]
        l2 = [self.city_x[a2], self.city_y[a2], self.city_x[b2], self.city_y[b2]]
        v1 = (l1[0] - l2[0], l1[1] - l2[1])
        v2 = (l1[0] - l2[2], l1[1] - l2[3])
        v0 = (l1[0] - l1[2], l1[1] - l1[3])
        a = v0[0] * v1[1] - v0[1] * v1[0]
        b = v0[0] * v2[1] - v0[1] * v2[0]
        l1, l2 = l2, l1
        v1 = (l1[0] - l2[0], l1[1] - l2[1])
        v2 = (l1[0] - l2[2], l1[1] - l2[3])
        v0 = (l1[0] - l1[2], l1[1] - l1[3])
        c = v0[0] * v1[1] - v0[1] * v1[0]
        d = v0[0] * v2[1] - v0[1] * v2[0]
        if a * b < 0 and c * d < 0:
            return True
        else:
            return False

    def self_intersect(self, gene):
        edges, cross_edges = [], []
        if self.sale_num == 1:
            for i in range(len(gene)):
                edges.append([gene[i], gene[(i + 1) % len(gene)]])
        else:
            for route in gene:
                for i in range(len(route)):
                    edges.append([route[i], route[(i + 1) % len(route)]])
        for i in range(len(edges) - 1):
            for j in range(i + 1, len(edges)):
                if self.intersect(edges[i], edges[j]):
                    cross_edges.append([edges[i], edges[j]])
        return cross_edges

    def intersection_fix(self, routes):
        cross_edges = self.self_intersect(routes)
        while cross_edges:
            edges = self.route2edges(routes)
            for i in cross_edges:
                edges.remove(i[0])
                edges.remove(i[1])
                edges.append([i[0][0], i[1][0]])
                edges.append([i[0][1], i[1][1]])
                break
            routes = self.edges2route(edges)
            cross_edges = self.self_intersect(routes)
        return routes

    def three_opt(self, route):
        n = len(route)
        flag = 1
        while flag == 1:
            flag = 0
            for i in range(n - 1):
                for j in range(i + 1, n):
                    for k in range(j + 1, n + 1):
                        routes = [[] for _ in range(8)]
                        routes[0] = route
                        routes[1] = route[:i] + route[i:j][::-1] + route[j:k] + route[k:]
                        routes[2] = route[:i] + route[i:j] + route[j:k][::-1] + route[k:]
                        routes[3] = route[:i] + route[j:k] + route[i:j][::-1] + route[k:]
                        routes[4] = route[:i] + route[j:k][::-1] + route[i:j][::-1] + route[k:]
                        routes[5] = route[:i] + route[j:k][::-1] + route[i:j] + route[k:]
                        routes[6] = route[:i] + route[i:j][::-1] + route[j:k][::-1] + route[k:]
                        routes[7] = route[:i] + route[j:k] + route[i:j] + route[k:]
                        route_dis = [calculate_distance(self.Distance, i) for i in routes]
                        best = route_dis.index(min(route_dis))
                        if best:
                            route = routes[best]
                            flag = 1
                            break
                        if flag == 1:
                            break
                    if flag == 1:
                        break
                if flag == 1:
                    break
        return route
